1. Draper N R and Smith H, xe2x80x9cApplied Regression Analysisxe2x80x9d, John Wiley and Sons, Inc., 1966, PP. 7-13.
2. Duda, R O and Hart P E, xe2x80x9cPattern Classification and Scene Analysis,xe2x80x9d John Wiley and Sons, New York, 1973, PP. 332-335.
3. Haralick R M and Shapiro, L G, xe2x80x9cSurvey Image Segmentation Techniques,xe2x80x9d Comput. Vision, Graphics Image Processing, vol. 29: 100-132, 1985.
4. Silver, B, xe2x80x9cGeometric Pattern Matching for General-Purpose Inspection in Industrial Machine Visionxe2x80x9d, Intelligent Vision ""99 Conferencexe2x80x94June 28-29, 1999.
This invention relates to high accuracy image processing, specifically to an improved method for measuring objects in an image with sub-pixel accuracy and repeatability.
Many computer vision applications require accurate and robust measurements of image features to detect defects or gather process statistics. The capability of a computer vision system is often characterized by its detection/measurement accuracy, repeatability and throughput. It is desirable to achieve sub-pixel measurement accuracy and repeatability for many computer vision applications.
Application domain knowledge is available in most computer vision applications. The application domain knowledge can often be expressed as structures of image features such as edges, lines and regions. The structures include spatial relationships of object features such as shape, size, intensity distribution, parallelism, co-linearity, adjacency, etc. The structure information can be well defined in industrial applications such as semiconductor, electronic or machine part inspections. In machine part inspections, most of the work-pieces have available Computer Aided Design (CAD) data that specifies its components as entities (LINE, POINT, 3DFACE, 3DPOLYLINE, 3DVERTEX, LINE, POINT, 3DFACE, 3DPOLYLINE, 3DVERTEX, etc.) and blocks of entities. In biomedical or scientific applications, structure information can often be loosely defined. For example, a cell nucleus is round and different shapes can differentiate different types of blood cells or chromosomes.
Application domain knowledge can significantly improve the measurement capability of a computer vision system. However, it is non-trivial to efficiently use the application domain knowledge in high precision applications that require sub-pixel accuracy, repeatability and real-time throughput.
An image segmentation approach is used in the prior art for image feature detection or measurement. The image segmentation approach converts a grayscale image into a binary image that contains object of interest masks. Binary thresholding is a common technique in the image segmentation approach (Haralick R M and Shapiro, L G, xe2x80x9cSurvey Image Segmentation Techniques,xe2x80x9d Comput. Vision, Graphics Image Processing, vol. 29: 100-132, 1985).
Image features such as edges in an image are smeared over a distance of four or five pixels, an effect that is the result of a reasonably sufficient sampling basis, imperfections in the camera optics, and the inevitability of physical laws (finite point spread function). Because edges or features of an image are imaged by the optical and imaging system as continuously varying gray levels, there exists no single gray level that represents edge pixels. For this reason, any system that depends on segmentation or a binary thresholding of the image before critical dimensions are determined must necessarily introduce quantization errors into the measurement. Binary thresholding also exacerbates the resolution limiting effect of system noise. Pixels whose gray levels are close to the threshold level are maximally affected by small variations due to additive noise. They may either be included or excluded into the mask based on the noise contribution to their instantaneous value. These pixels are frequently located on the periphery of the part, or a substructure of the part, where they have maximal disruption of the derived measurement values.
Prior art (Silver, B, xe2x80x9cGeometric Pattern Matching for General-Purpose Inspection in Industrial Machine Visionxe2x80x9d, Intelligent Vision ""99 Conferencexe2x80x94Jun. 28-29, 1999) applies application domain structure information using a template matching method. An image of the object to be located (the template) is stored. The template is compared to similar sized regions of the image over a range of positions, with the position of greatest match taken to be the position of the object and measurements are conducted between the detected positions. Template matching does not provide sub-pixel accuracy and repeatability since the estimated positions lie in pixel grids that exhibit spatial quantization error due to limitations in pixel pitch. Furthermore, the template matching approach is sensitive to variations such as orientation and size differences between the image and the template. Even within a small range of size and orientation changes, the match value drops off rapidly and the ability to locate and measure image features drops with it.
Prior art applies application domain structure information through a projection/dispersion approach. The projection/dispersion approach integrates (projects) image pixel values over a pre-defined direction in the image. This can be done for binary image (projection) or grayscale image (dispersion) and results in a one-dimensional line of values. The application domain structure information defines the projection directions. However, the prior art approach is sensitive to system variations such as rotation. Rotation effect could result in the integration of pixel values along a wrong direction that is destructive to sub-pixel accuracies. Furthermore, the projection approach cannot effectively combine multiple two-dimensional (or more dimensions) structure information where features of interest are along different directions. Therefore, only a limited number of image pixels (n) are used for feature estimation or measurement. Measurement uncertainty is related to       1          n        .
Smaller n results in bigger uncertainty or lower accuracy.
Certain pixels in image feature region are more indicative than others. However, the prior art approach does not take advantage of this information. Projection treats edge pixels and region pixels with equal weight. Prior Art does not score the reliability of each measurement. Prior Art does not do additional processing to improve accuracy and repeatability on less reliable measurements. This is difficult to accomplish since most prior art measurements are done in an ad hoc fashion.
It is an object of this invention to provide sub-pixel image feature estimation and measurement by using structure-guided image processing techniques. The results of the structure-guided estimation is symbolic representation of geometry entities such as lines, points, arcs and circles. The symbolic representation is not limited by image resolution or pixel quantization error and therefore facilitates sub-pixel measurements. The image feature estimation is based on grayscale weights rather than a binary (mask) image.
It is another object of the invention to conduct the estimation in at least two dimensions to avoid error caused by one-dimensional projection and to utilize gray scale processing based on the weighted image within feature transition regions.
A further object of the invention is to guide the image feature estimation by structure constraints defined from application domain knowledge to increase accuracy. Accuracy is increased by using structure constraints to link multiple features for an integrated estimation that utilizes a large number of pixels (large n). Large n reduces the measurement error and increases measurement repeatability.
It is a still further object of the invention to score measurement reliability and guided by the scores, improve accuracy and repeatability using an iterative estimation approach.
It is an object of this invention to allow learning to determine the importance and stability of image pixels and weight important and stable pixels higher in the estimation process.
This invention provides sub-pixel, high performance image based estimation and measurement through a structure-guided image processing method. In the preferred embodiment, this invention performs two dimensional geometry estimation using images of grayscale weights for each connected component in the measurement mask. The features from which the masks and the weights are derived are described in the co-pending U. S. Patent Application entitled, xe2x80x9cStructure-guided Image Processing and Image Feature Enhancementxe2x80x9d by Shih-Jong J. Lee, filed Dec. 15, 2000 which is incorporated herein in its entirety.
Results of the structure-guided estimation are symbolic representation of geometry entities such as lines, points, arcs and circles. The symbolic representation facilitates sub-pixel measurements by increasing the number of pixels used in the matching of image features to structural entities, improving the detection of structural entities within the image, weighting the contribution of each image sample to the measurement that is being made and optimizing that contribution.
After the structure-guided estimation, geometric entities are represented by their symbolic representations. Structure-guided measurements can be conducted using the symbolic representation of geometric entities. Measurements performed from the symbolic representation are not limited by image resolution or pixel quantization error and therefore can yield sub-pixel accuracy and repeatability.